package com.github.hgkmail.hello.leetcode101.pointer.linkedlist;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;
import com.github.hgkmail.hello.leetcode101.base.ListNode;

public class LC19RemoveNthNodeFromEndOfList {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head==null) {
            return head;
        }
        ListNode dummyHead=new ListNode(0, head);
        int len=0;
        ListNode curr=head;
        while (curr!=null) {
            len+=1;
            curr=curr.next;
        }
        int removeIndex=len-n;
        int i=0;
        curr=head;
        ListNode prev=dummyHead;
        while (curr!=null && i<removeIndex) {
            prev=curr;
            curr=curr.next;
            i++;
        }
        prev.next = curr!=null ? curr.next : null;

        return dummyHead.next;
    }

    //先后指针
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        if (head==null) {
            return head;
        }
        ListNode dummyHead=new ListNode(0, head);
        ListNode first=dummyHead, second=dummyHead;
        //first先走n步
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        //first和second同时走
        while (first.next!=null) { //必须是有效步数
            first=first.next;
            second=second.next;
        }
        ListNode nodeToDelete = second.next;
        second.next=nodeToDelete.next;

        return dummyHead.next;
    }

    public static void main(String[] args) {
        ListNode a=new ListNode(5, null);
        ListNode b=new ListNode(4, a);
        ListNode c=new ListNode(3, b);
        ListNode d=new ListNode(2, c);
        ListNode e=new ListNode(1, d);
        CommonUtil.printLinkedList(new LC19RemoveNthNodeFromEndOfList().removeNthFromEnd2(e, 2));
    }
}
